Cook-Levin theorem

Theorem

1. SAT is NP-complete
2. 3SAT is NP-complete

Notes

• NP-complete Boolean satisfiability problem
• 2SAT is in P
• kSAT is NP-complete for $k \geq 3$

See also

• P versus NP problem

References

1. https://www.cs.williams.edu/~shikha/teaching/spring20/cs256/lectures/Lecture22.pdf
2. https://people.csail.mit.edu/virgi/6.1420/lecture1.pdf